package LeetCode;

public class Code53_maxSubArray {
    //1.暴力法
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int temp = 0;
            for (int j = i; j < nums.length; j++) {
                temp += nums[j];
                max = Math.max(max, temp);
            }
        }
        return max > 0 ? max : 0;
    }

    // 2.动态规划:以当前元素为末尾，考虑加不加之前的连续子数组和
    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > 0){
                nums[i] += nums[i - 1];
            }
            max = Math.max(max, nums[i]);
        }
        return max;
    }


    public static void main(String[] args) {
        Code53_maxSubArray code53_maxSubArray = new Code53_maxSubArray();
        System.out.println(code53_maxSubArray.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
        System.out.println(code53_maxSubArray.maxSubArray2(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
